SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Constraint programming</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Constraint programming</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p><b>Constraint programming (CP)</b><sup id="cite_ref-:0_1-0" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> is a paradigm for solving <a href="Combinatorial" class="mw-redirect" title="Combinatorial">combinatorial</a> problems that draws on a wide range of techniques from <a href="Artificial_intelligence" title="Artificial intelligence">artificial intelligence</a>, <a href="Computer_science" title="Computer science">computer science</a>, and <a href="Operations_research" title="Operations research">operations research</a>. In constraint programming, users declaratively state the <a href="Constraint_(mathematics)" title="Constraint (mathematics)">constraints</a> on the feasible solutions for a set of decision variables. Constraints differ from the common <a href="Language_primitive" title="Language primitive">primitives</a> of <a href="Imperative_programming" title="Imperative programming">imperative programming</a> languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. In addition to constraints, users also need to specify a method to solve these constraints. This typically draws upon standard methods like chronological <a href="Backtracking" title="Backtracking">backtracking</a> and <a href="Constraint_propagation" class="mw-redirect" title="Constraint propagation">constraint propagation</a>, but may use customized code like a problem-specific branching <a href="Heuristic_(computer_science)" title="Heuristic (computer science)">heuristic</a>.

</p><p>Constraint programming takes its root from and can be expressed in the form of <a href="Constraint_logic_programming" title="Constraint logic programming">constraint logic programming</a>, which embeds constraints into a <a href="Logic_program" class="mw-redirect" title="Logic program">logic program</a>. This variant of logic programming is due to Jaffar and Lassez,<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> who extended in 1987 a specific class of constraints that were introduced in <a href="Prolog_II" class="mw-redirect" title="Prolog II">Prolog II</a>. The first implementations of constraint logic programming were Prolog III, <a href="CLP(R)" title="CLP(R)">CLP(R)</a>, and <a href="CHIP_(programming_language)" title="CHIP (programming language)">CHIP</a>.

</p><p>Instead of logic programming, constraints can be mixed with <a href="Functional_programming" title="Functional programming">functional programming</a>, <a href="Term_rewriting" class="mw-redirect" title="Term rewriting">term rewriting</a>, and <a href="Imperative_language" class="mw-redirect" title="Imperative language">imperative languages</a>.

Programming languages with built-in support for constraints include <a href="Oz_programming_language" class="mw-redirect" title="Oz programming language">Oz</a> (functional programming) and <a href="Kaleidoscope_programming_language" class="mw-redirect" title="Kaleidoscope programming language">Kaleidoscope</a> (imperative programming). Mostly, constraints are implemented in imperative languages via <i>constraint solving toolkits</i>, which are separate libraries for an existing imperative language.

</p>

<div class="mw-heading mw-heading2"><h2 id="Constraint_logic_programming">Constraint logic programming</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Constraint_logic_programming" title="Constraint logic programming">Constraint logic programming</a></div>

<p>Constraint programming is an embedding of constraints in a host language. The first host languages used were <a href="Logic_programming" title="Logic programming">logic programming</a> languages, so the field was initially called <i>constraint logic programming</i>. The two paradigms share many important features, like logical variables and <a href="Backtracking" title="Backtracking">backtracking</a>. Today most <a href="Prolog" title="Prolog">Prolog</a> implementations include one or more libraries for constraint logic programming.

</p><p>The difference between the two is largely in their styles and approaches to modeling the world. Some problems are more natural (and thus, simpler) to write as logic programs, while some are more natural to write as constraint programs.

</p><p>The constraint programming approach is to search for a state of the world in which a large number of constraints are satisfied at the same time. A problem is typically stated as a state of the world containing a number of unknown variables. The constraint program searches for values for all the variables.

</p><p>Temporal concurrent constraint programming (TCC) and non-deterministic temporal concurrent constraint programming (MJV) are variants of constraint programming that can deal with time.

</p>

<div class="mw-heading mw-heading2"><h2 id="Constraint_satisfaction_problem">Constraint satisfaction problem</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">Constraint satisfaction problem</a></div>

<p>A constraint is a relation between multiple variables that limits the values these variables can take simultaneously.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_theorem{margin:1em 2em;padding:0.5em 1em 0.4em;border:1px solid #aaa;overflow:hidden}@media(max-width:500px){.mw-parser-output .math_theorem{margin:1em 0em;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_theorem" style="">

<p><strong class="theorem-name">Definition</strong><span class="theoreme-tiret">—</span>A constraint satisfaction problem on finite domains (or CSP) is defined by a triplet <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}</annotation>

</semantics>

</math></span><img src="./3237213200e8e80327a2cb23f816fe23fc2b1758.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.784ex; height:2.843ex;" alt="{\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}" loading="lazy"></span> where:

</p>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}}</annotation>

</semantics>

</math></span><img src="./9c79de31ad45cb5aace78239e9847704dc199bf2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.409ex; height:2.843ex;" alt="{\displaystyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}}" loading="lazy"></span> is the set of variables of the problem;</li>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}}</annotation>

</semantics>

</math></span><img src="./ea456803849d9f891d5910dd6091f779456e4cf1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.25ex; height:2.843ex;" alt="{\displaystyle {\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}}" loading="lazy"></span> is the set of domains of the variables, i.e., for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in [1;n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in [1;n]}</annotation>

</semantics>

</math></span><img src="./78ea62ce2b991a37832013971da14249ad23d4a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.937ex; height:2.843ex;" alt="{\displaystyle k\in [1;n]}" loading="lazy"></span> we have <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{k}\in {\mathcal {D}}_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{k}\in {\mathcal {D}}_{k}}</annotation>

</semantics>

</math></span><img src="./93deb346f5f094f2cd5a8aea339eea8f35982cf8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.14ex; height:2.509ex;" alt="{\displaystyle x_{k}\in {\mathcal {D}}_{k}}" loading="lazy"></span>;</li>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {C}}=\{C_{1},\dots ,C_{m}\}}</annotation>

</semantics>

</math></span><img src="./c6d186587e0e71e0356c3a0d73deeb0afed1b258.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.894ex; height:2.843ex;" alt="{\displaystyle {\mathcal {C}}=\{C_{1},\dots ,C_{m}\}}" loading="lazy"></span> is a set of constraints. A constraint <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}</annotation>

</semantics>

</math></span><img src="./601ef4a2e073b8538ffe0f023b5e5ddd44583657.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.63ex; height:2.843ex;" alt="{\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}" loading="lazy"></span> is defined by a set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}</annotation>

</semantics>

</math></span><img src="./b8108ca8e347349c0b28035e04974f80453bb8f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:19.008ex; height:3.009ex;" alt="{\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}" loading="lazy"></span> of variables and a relation <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}</annotation>

</semantics>

</math></span><img src="./4163a6dad596cee235dbd4c60632ae73f0aeddc1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.147ex; height:2.843ex;" alt="{\displaystyle {\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}" loading="lazy"></span> that defines the set of values allowed simultaneously for the variables of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {X}}_{i}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {X}}_{i}}</annotation>

</semantics>

</math></span><img src="./f3603a034f3120170f526ebd3534cb80d5c8158a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.457ex; height:2.509ex;" alt="{\displaystyle {\mathcal {X}}_{i}}" loading="lazy"></span>.</li></ul>

</div>

<p>Three categories of constraints exist:

</p>

<ul><li>extensional constraints: constraints are defined by enumerating the set of values that would satisfy them;</li>

<li>arithmetic constraints: constraints are defined by an arithmetic expression, i.e., using <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle <,>,\leq ,\geq ,=,\neq ,...}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle <,>,\leq ,\geq ,=,\neq ,...}</annotation>

</semantics>

</math></span><img src="./eeaddf2fabe17a627fbecb6b7278cdf2949be72f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.767ex; height:2.676ex;" alt="{\displaystyle <,>,\leq ,\geq ,=,\neq ,...}" loading="lazy"></span>;</li>

<li>logical constraints: constraints are defined with an explicit semantics, i.e., <i>AllDifferent</i>, <i>AtMost</i>,<i>...</i></li></ul>

<p><strong class="theorem-name">Definition</strong><span class="theoreme-tiret">—</span> An assignment (or model) <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}}</annotation>

</semantics>

</math></span><img src="./280ae03440942ab348c2ca9b8db6b56ffa9618f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.903ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}}" loading="lazy"></span> of a CSP <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}</annotation>

</semantics>

</math></span><img src="./29b86d87be22c427cd9f926344de63e8086c8ac3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.628ex; height:2.843ex;" alt="{\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}" loading="lazy"></span> is defined by the couple <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}</annotation>

</semantics>

</math></span><img src="./34da36fc4fdbf77b012ac37ed7eb0a0a13e02c12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.083ex; height:2.843ex;" alt="{\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}" loading="lazy"></span> where:

</p>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}}</annotation>

</semantics>

</math></span><img src="./ada220462ad690be52c3c346b2f4f342ee763a00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.209ex; height:2.509ex;" alt="{\displaystyle {\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}}" loading="lazy"></span> is a subset of variable;</li>

<msub>

</mrow>

</msub>

</mrow>

<msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}}</annotation>

</semantics>

</math></span><img src="./7f7b693d54d7d96101a395f5bd5e7ca7680f4171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:39.344ex; height:3.009ex;" alt="{\displaystyle {\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}}" loading="lazy"></span> is the tuple of the values taken by the assigned variables.</li></ul>

</div>

<p>Assignment is the association of a variable to a value from its domain. A partial assignment is when a subset of the variables of the problem has been assigned. A total assignment is when all the variables of the problem have been assigned.

</p>

<p><strong class="theorem-name">Property</strong><span class="theoreme-tiret">—</span>Given <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}">

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}</annotation>

</semantics>

</math></span><img src="./34da36fc4fdbf77b012ac37ed7eb0a0a13e02c12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.083ex; height:2.843ex;" alt="{\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}" loading="lazy"></span> an assignment (partial or total) of a CSP <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}">

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}</annotation>

</semantics>

</math></span><img src="./29b86d87be22c427cd9f926344de63e8086c8ac3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.628ex; height:2.843ex;" alt="{\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}" loading="lazy"></span>, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}</annotation>

</semantics>

</math></span><img src="./601ef4a2e073b8538ffe0f023b5e5ddd44583657.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.63ex; height:2.843ex;" alt="{\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}" loading="lazy"></span> a constraint of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> such as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}}</annotation>

</semantics>

</math></span><img src="./8fa97532fdb785fe82f3a53b87b2f76f363bed1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.791ex; height:2.509ex;" alt="{\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}}" loading="lazy"></span>, the assignment <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}}</annotation>

</semantics>

</math></span><img src="./280ae03440942ab348c2ca9b8db6b56ffa9618f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.903ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}}" loading="lazy"></span> satisfies the constraint <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math></span><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy"></span> if and only if all the values <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ such that }}x_{i}\in {\mathcal {X}}_{i}\}}">

<msub>

</mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ such that }}x_{i}\in {\mathcal {X}}_{i}\}}</annotation>

</semantics>

</math></span><img src="./6784abcdcdc34ab58a68023657cba90a4ad1bca0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:34.755ex; height:3.009ex;" alt="{\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ such that }}x_{i}\in {\mathcal {X}}_{i}\}}" loading="lazy"></span> of the variables of the constraint <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{i}}</annotation>

</semantics>

</math></span><img src="./cc49dc02c0ec8c86b67e7d10518ac791eda0bf22.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.461ex; height:2.509ex;" alt="{\displaystyle C_{i}}" loading="lazy"></span> belongs to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {R}}_{i}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {R}}_{i}}</annotation>

</semantics>

</math></span><img src="./ea4e99f70ce55a732f202d636b5fdc6a28e13440.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.77ex; height:2.509ex;" alt="{\displaystyle {\mathcal {R}}_{i}}" loading="lazy"></span>.

</p>

</div>

<p><strong class="theorem-name">Definition</strong><span class="theoreme-tiret">—</span>A solution of a CSP is a total assignment that satisfies all the constraints of the problem.

</p>

</div>

<p>During the search of the solutions of a CSP, a user can wish for:

</p>

<ul><li>finding a solution (satisfying all the constraints);</li>

<li>finding all the solutions of the problem;</li>

<li><a href="Automated_theorem_proving" title="Automated theorem proving">proving</a> the unsatisfiability of the problem.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Constraint_optimization_problem">Constraint optimization problem</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Constrained_optimization" title="Constrained optimization">Constrained optimization</a></div>

<p>A constraint optimization problem (COP) is a constraint satisfaction problem associated to an objective function.

</p><p>An <i>optimal solution</i> to a minimization (maximization) COP is a solution that minimizes (maximizes) the value of the <i>objective function</i>.

</p><p>During the search of the solutions of a COP, a user can wish for:

</p>

<ul><li>finding a solution (satisfying all the constraints);</li></ul>

<ul><li>finding the best solution with respect to the objective;</li>

<li>proving the optimality of the best found solution;</li>

<li>proving the unsatisfiability of the problem.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Perturbation_vs_refinement_models">Perturbation vs refinement models</h2></div>

<p>Languages for constraint-based programming follow one of two approaches:<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li>Refinement model: variables in the problem are initially unassigned, and each variable is assumed to be able to contain any value included in its range or domain. As computation progresses, values in the domain of a variable are pruned if they are shown to be incompatible with the possible values of other variables, until a single value is found for each variable.</li>

<li>Perturbation model: variables in the problem are assigned a single initial value. At different times one or more variables receive perturbations (changes to their old value), and the system propagates the change trying to assign new values to other variables that are consistent with the perturbation.</li></ul>

<p><a href="Constraint_propagation" class="mw-redirect" title="Constraint propagation">Constraint propagation</a> in <a href="Constraint_Satisfaction_Problems" class="mw-redirect" title="Constraint Satisfaction Problems">constraint satisfaction problems</a> is a typical example of a refinement model, and formula evaluation in <a href="Spreadsheet" title="Spreadsheet">spreadsheets</a> are a typical example of a perturbation model.

</p><p>The refinement model is more general, as it does not restrict variables to have a single value, it can lead to several solutions to the same problem. However, the perturbation model is more intuitive for programmers using mixed imperative constraint object-oriented languages.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Domains">Domains</h2></div>

<p>The constraints used in constraint programming are typically over some specific domains. Some popular domains for constraint programming are:

</p>

<ul><li><a href="Boolean_data_type" title="Boolean data type">Boolean</a> domains, where only true/false constraints apply (<a href="Boolean_satisfiability_problem" title="Boolean satisfiability problem">SAT problem</a>)</li>

<li><a href="Integer" title="Integer">integer</a> domains, <a href="Rational_numbers" class="mw-redirect" title="Rational numbers">rational</a> domains</li>

<li><a href="Interval_(mathematics)" title="Interval (mathematics)">interval</a> domains, in particular for <a href="Automated_planning_and_scheduling" title="Automated planning and scheduling">scheduling</a> problems<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Linear_algebra" title="Linear algebra">linear</a> domains, where only <a href="Linear" class="mw-redirect" title="Linear">linear</a> functions are described and analyzed (although approaches to <a href="Non-linear" class="mw-redirect" title="Non-linear">non-linear</a> problems do exist)</li>

<li><a href="https://en.wiktionary.org/wiki/finite" class="extiw external" title="wiktionary:finite">finite</a> domains, where constraints are defined over <a href="Finite_set" title="Finite set">finite sets</a></li>

<li>mixed domains, involving two or more of the above</li></ul>

<p>Finite domains is one of the most successful domains of constraint programming. In some areas (like <a href="Operations_research" title="Operations research">operations research</a>) constraint programming is often identified with constraint programming over finite domains.

</p>

<div class="mw-heading mw-heading2"><h2 id="Constraint_propagation">Constraint propagation</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Constraint_propagation" class="mw-redirect" title="Constraint propagation">Constraint propagation</a></div>

<p><b>Local consistency</b> conditions are properties of <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">constraint satisfaction problems</a> related to the <a href="Consistency" title="Consistency">consistency</a> of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including <b>node consistency</b>, <b>arc consistency</b>, and <b>path consistency</b>.

</p><p>Every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions. Such a transformation is called <b><a href="Constraint_propagation" class="mw-redirect" title="Constraint propagation">constraint propagation</a></b>.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Constraint propagation works by reducing domains of variables, strengthening constraints, or creating new ones. This leads to a reduction of the search space, making the problem easier to solve by some algorithms. Constraint propagation can also be used as an unsatisfiability checker, incomplete in general but complete in some particular cases.

</p>

<div class="mw-heading mw-heading2"><h2 id="Constraint_solving">Constraint solving</h2></div>

<p>There are three main algorithmic techniques for solving constraint satisfaction problems: backtracking search, local search, and dynamic programming.<sup id="cite_ref-:0_1-1" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Backtracking_search">Backtracking search</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Backtracking" title="Backtracking">Backtracking</a></div>

<p><b>Backtracking search</b> is a general <a href="Algorithm" title="Algorithm">algorithm</a> for finding all (or some) solutions to some <a href="Computational_problem" title="Computational problem">computational problems</a>, notably <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">constraint satisfaction problems</a>, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution.

</p>

<div class="mw-heading mw-heading3"><h3 id="Local_Search">Local Search</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Local_search_(constraint_satisfaction)" title="Local search (constraint satisfaction)">Local search (constraint satisfaction)</a></div>

<p><b>Local search</b> is an incomplete method for finding a solution to a <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">problem</a>. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms typically modify the value of a variable in an assignment at each step. The new assignment is close to the previous one in the space of assignment, hence the name <i>local search</i>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Dynamic_programming">Dynamic programming</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></div>

<p><b>Dynamic programming</b> is both a <a href="Mathematical_optimization" title="Mathematical optimization">mathematical optimization</a> method and a computer programming method. It refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a <a href="Recursion" title="Recursion">recursive</a> manner. While some <a href="Decision_problem" title="Decision problem">decision problems</a> cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have <a href="Optimal_substructure" title="Optimal substructure">optimal substructure</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<p>The syntax for expressing constraints over finite domains depends on the host language. The following is a <a href="Prolog" title="Prolog">Prolog</a> program that solves the classical <a href="Alphametic" class="mw-redirect" title="Alphametic">alphametic</a> puzzle SEND+MORE=MONEY in constraint logic programming:

</p>

<div class="mw-highlight mw-highlight-lang-prolog mw-content-ltr" dir="ltr"><pre><span class="c1">% This code works in both YAP and SWI-Prolog using the environment-supplied</span>

<span class="c1">% CLPFD constraint solver library. It may require minor modifications to work</span>

<span class="c1">% in other Prolog environments or using other constraint solvers.</span>

<span class="p">:-</span> <span class="nf">use_module</span><span class="p">(</span><span class="nf">library</span><span class="p">(</span><span class="s s-Atom">clpfd</span><span class="p">)).</span>

<span class="nf">sendmore</span><span class="p">(</span><span class="nv">Digits</span><span class="p">)</span> <span class="p">:-</span>

<span class="nv">Digits</span> <span class="o">=</span> <span class="p">[</span><span class="nv">S</span><span class="p">,</span><span class="nv">E</span><span class="p">,</span><span class="nv">N</span><span class="p">,</span><span class="nv">D</span><span class="p">,</span><span class="nv">M</span><span class="p">,</span><span class="nv">O</span><span class="p">,</span><span class="nv">R</span><span class="p">,</span><span class="nv">Y</span><span class="p">],</span> <span class="c1">% Create variables</span>

<span class="nv">Digits</span> <span class="s s-Atom">ins</span> <span class="mf">0..9</span><span class="p">,</span> <span class="c1">% Associate domains to variables</span>

<span class="nv">S</span> <span class="s s-Atom">#\=</span> <span class="mi">0</span><span class="p">,</span> <span class="c1">% Constraint: S must be different from 0</span>

<span class="nf">all_different</span><span class="p">(</span><span class="nv">Digits</span><span class="p">),</span> <span class="c1">% all the elements must take different values</span>

<span class="mi">1000</span><span class="o">*</span><span class="nv">S</span> <span class="o">+</span> <span class="mi">100</span><span class="o">*</span><span class="nv">E</span> <span class="o">+</span> <span class="mi">10</span><span class="o">*</span><span class="nv">N</span> <span class="o">+</span> <span class="nv">D</span> <span class="c1">% Other constraints</span>

<span class="nf">label</span><span class="p">(</span><span class="nv">Digits</span><span class="p">).</span> <span class="c1">% Start the search</span>

</pre></div>

<p>The interpreter creates a variable for each letter in the puzzle. The operator <code>ins</code> is used to specify the domains of these variables, so that they range over the set of values {0,1,2,3, ..., 9}. The constraints <code>S#\=0</code> and <code>M#\=0</code> means that these two variables cannot take the value zero. When the interpreter evaluates these constraints, it reduces the domains of these two variables by removing the value 0 from them. Then, the constraint <code>all_different(Digits)</code> is considered; it does not reduce any domain, so it is simply stored. The last constraint specifies that the digits assigned to the letters must be such that "SEND+MORE=MONEY" holds when each letter is replaced by its corresponding digit. From this constraint, the solver infers that M=1. All stored constraints involving variable M are awakened: in this case, <a href="Constraint_propagation" class="mw-redirect" title="Constraint propagation">constraint propagation</a> on the <code>all_different</code> constraint removes value 1 from the domain of all the remaining variables. Constraint propagation may solve the problem by reducing all domains to a single value, it may prove that the problem has no solution by reducing a domain to the empty set, but may also terminate without proving satisfiability or unsatisfiability. The <b>label</b> literals are used to actually perform search for a solution.

</p>

<ul><li><a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial optimization</a></li>

<li><a href="Concurrent_constraint_logic_programming" title="Concurrent constraint logic programming">Concurrent constraint logic programming</a></li>

<li><a href="Constraint_logic_programming" title="Constraint logic programming">Constraint logic programming</a></li>

<li><a href="Heuristic_(computer_science)" title="Heuristic (computer science)">Heuristic algorithms</a></li>

<li><a href="List_of_constraint_programming_languages" class="mw-redirect" title="List of constraint programming languages">List of constraint programming languages</a></li>

<li><a href="Mathematical_optimization" title="Mathematical optimization">Mathematical optimization</a></li>

<li><a href="Nurse_scheduling_problem" title="Nurse scheduling problem">Nurse scheduling problem</a></li>

<li><a href="Regular_constraint" title="Regular constraint">Regular constraint</a></li>

<li><a href="Satisfiability_modulo_theories" title="Satisfiability modulo theories">Satisfiability modulo theories</a></li>

<li><a href="Traveling_tournament_problem" title="Traveling tournament problem">Traveling tournament problem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFRossiBeekWalsh2006" class="citation book cs1"><a href="Francesca_Rossi" title="Francesca Rossi">Rossi, Francesca</a>; Beek, Peter van; <a href="Toby_Walsh" title="Toby Walsh">Walsh, Toby</a> (2006-08-18). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Kjap9ZWcKOoC&q=handbook+of+constraint+programming&pg=PP1"><i>Handbook of Constraint Programming</i></a>. Elsevier. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780080463803</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Jaffar, Joxan, and J-L. Lassez. "<a rel="nofollow" class="external text" href="https://dl.acm.org/citation.cfm?id=41635">Constraint logic programming</a>." Proceedings of the 14th <a href="ACM_SIGPLAN-SIGACT_Symposium_on_Principles_of_Programming_Languages" class="mw-redirect" title="ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages">ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages</a>. ACM, 1987.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFMayohTyuguPenjam1993" class="citation book cs1">Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=B0aqCAAAQBAJ"><i>Constraint Programming</i></a>. <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer Science+Business Media</a>. p. 76. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783642859830</bdi>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">Lopez, G., Freeman-Benson, B., & Borning, A. (1994, January). <a rel="nofollow" class="external text" href="ftp://trout.cs.washington.edu/tr/1993/09/UW-CSE-93-09-04.pdf">Kaleidoscope: A constraint imperative programming language.</a> In <i>Constraint Programming</i> (pp. 313-329). Springer Berlin Heidelberg.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFBaptistePapeNuijten2012" class="citation book cs1"><a href="Philippe_Baptiste" title="Philippe Baptiste">Baptiste, Philippe</a>; Pape, Claude Le; Nuijten, Wim (2012-12-06). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=qUzhBwAAQBAJ"><i>Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems</i></a>. Springer Science & Business Media. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4615-1479-4</bdi>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFBessiere2006" class="citation cs2">Bessiere, Christian (2006), "Constraint Propagation", <i>Handbook of Constraint Programming</i>, Foundations of Artificial Intelligence, vol. 2, Elsevier, pp. <span class="nowrap">29–</span>83, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.398.4070">10.1.1.398.4070</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs1574-6526%2806%2980007-6">10.1016/s1574-6526(06)80007-6</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780444527264</bdi></cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Constraint_programming" class="extiw external" title="commons:Category:Constraint programming">Constraint programming</a></span>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="http://www.a4cp.org/">Association for Constraint Programming</a></li>

<li><a rel="nofollow" class="external text" href="http://www.a4cp.org/events/cp-conference-series">CP Conference Series</a></li>

<li><a rel="nofollow" class="external text" href="http://kti.ms.mff.cuni.cz/~bartak/constraints/">Guide to Constraint Programming</a></li>

<li><a rel="nofollow" class="external text" href="https://archive.today/20121205051244/http://www.mozart-oz.org/">The Mozart Programming System</a> at <a href="Archive.today" title="Archive.today">archive.today</a> (archived December 5, 2012), an <a href="Oz_(programming_language)" title="Oz (programming language)">Oz</a>-based free software (<a href="X_Window_System" title="X Window System">X Window System</a> style)</li>

<li><a rel="nofollow" class="external text" href="https://archive.today/20130107222548/http://4c.ucc.ie/web/index.jsp">Cork Constraint Computation Centre</a> at <a href="Archive.today" title="Archive.today">archive.today</a> (archived January 7, 2013)</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Programming_paradigms_(Comparison_by_language)368" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Programming_paradigms_(Comparison_by_language)368" style="font-size:114%;margin:0 4em"><a href="Programming_paradigm" title="Programming paradigm">Programming paradigms</a> (<a href="Comparison_of_multi-paradigm_programming_languages" title="Comparison of multi-paradigm programming languages">Comparison by language</a>)</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Imperative_programming" title="Imperative programming">Imperative</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Structured_programming" title="Structured programming">Structured</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Jackson_structured_programming" title="Jackson structured programming">Jackson structures</a></li>

<li><a href="Block_(programming)" title="Block (programming)">Block-structured</a></li>

<li><a href="Modular_programming" title="Modular programming">Modular</a></li>

<li><a href="Non-structured_programming" title="Non-structured programming">Non-structured</a></li>

<li><a href="Procedural_programming" title="Procedural programming">Procedural</a></li>

<li><a href="Programming_in_the_large_and_programming_in_the_small" title="Programming in the large and programming in the small">Programming in the large and in the small</a></li>

<li><a href="Design_by_contract" title="Design by contract">Design by contract</a></li>

<li><a href="Invariant-based_programming" title="Invariant-based programming">Invariant-based</a></li>

<li><a href="Nested_function" title="Nested function">Nested function</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Object-oriented_programming" title="Object-oriented programming">Object-oriented</a><br>(<a href="Comparison_of_programming_languages_(object-oriented_programming)" title="Comparison of programming languages (object-oriented programming)">comparison</a>, <a href="List_of_object-oriented_programming_languages" title="List of object-oriented programming languages">list</a>)</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Class-based_programming" title="Class-based programming">Class-based</a>, <a href="Prototype-based_programming" title="Prototype-based programming">Prototype-based</a>, <a href="Object-based_language" title="Object-based language">Object-based</a></li>

<li><a href="Agent-oriented_programming" title="Agent-oriented programming">Agent</a></li>

<li><a href="Immutable_object" title="Immutable object">Immutable object</a></li>

<li><a href="Persistent_programming_language" title="Persistent programming language">Persistent</a></li>

<li><a href="Uniform_function_call_syntax" title="Uniform function call syntax">Uniform function call syntax</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Declarative_programming" title="Declarative programming">Declarative</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Functional_programming" title="Functional programming">Functional</a><br>(<a href="Comparison_of_functional_programming_languages" title="Comparison of functional programming languages">comparison</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursive</a></li>

<li><a href="Anonymous_function" title="Anonymous function">Anonymous function</a> (<a href="Partial_application" title="Partial application">Partial application</a>)</li>

<li><a href="Higher-order_programming" title="Higher-order programming">Higher-order</a></li>

<li><a href="Purely_functional_programming" title="Purely functional programming">Purely functional</a></li>

<li><a href="Total_functional_programming" title="Total functional programming">Total</a></li>

<li><a href="Strict_programming_language" title="Strict programming language">Strict</a></li>

<li><a href="Generalized_algebraic_data_type" title="Generalized algebraic data type">GADTs</a></li>

<li><a href="Dependent_type" title="Dependent type">Dependent types</a></li>

<li><a href="Functional_logic_programming" title="Functional logic programming">Functional logic</a></li>

<li><a href="Tacit_programming" title="Tacit programming">Point-free style</a></li>

<li><a href="Expression-oriented_programming_language" title="Expression-oriented programming language">Expression-oriented</a></li>

<li><a href="Applicative_programming_language" title="Applicative programming language">Applicative</a>, <a href="Concatenative_programming_language" title="Concatenative programming language">Concatenative</a></li>

<li><a href="Function-level_programming" title="Function-level programming">Function-level</a>, <a href="Value-level_programming" title="Value-level programming">Value-level</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Dataflow_programming" title="Dataflow programming">Dataflow</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Flow-based_programming" title="Flow-based programming">Flow-based</a></li>

<li><a href="Reactive_programming" title="Reactive programming">Reactive</a> (<a href="Functional_reactive_programming" title="Functional reactive programming">Functional reactive</a>)</li>

<li><a href="Signal_programming" class="mw-redirect" title="Signal programming">Signals</a></li>

<li><a href="Stream_processing" title="Stream processing">Streams</a></li>

<li><a href="Synchronous_programming_language" title="Synchronous programming language">Synchronous</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Logic_programming" title="Logic programming">Logic</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abductive_logic_programming" title="Abductive logic programming">Abductive logic</a></li>

<li><a href="Answer_set_programming" title="Answer set programming">Answer set</a></li>

<li> (<a href="Constraint_logic_programming" title="Constraint logic programming">Constraint logic</a>)</li>

<li><a href="Inductive_logic_programming" title="Inductive logic programming">Inductive logic</a></li>

<li><a href="Nondeterministic_programming" title="Nondeterministic programming">Nondeterministic</a></li>

<li><a href="Ontology_language" title="Ontology language">Ontology</a></li>

<li><a href="Probabilistic_logic_programming" title="Probabilistic logic programming">Probabilistic logic</a></li>

<li><a href="Query_language" title="Query language">Query</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Domain-specific_language" title="Domain-specific language">DSL</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algebraic_modeling_language" title="Algebraic modeling language">Algebraic modeling</a></li>

<li><a href="Array_programming" title="Array programming">Array</a></li>

<li><a href="Automata-based_programming" title="Automata-based programming">Automata-based</a> (<a href="Action_language" title="Action language">Action</a>)</li>

<li><a href="Command_language" title="Command language">Command</a> (<a href="Spacecraft_command_language" title="Spacecraft command language">Spacecraft</a>)</li>

<li><a href="Differentiable_programming" title="Differentiable programming">Differentiable</a></li>

<li><a href="Grammar-oriented_programming" title="Grammar-oriented programming">Grammar-oriented</a></li>

<li><a href="Interface_description_language" title="Interface description language">Interface description</a></li>

<li><a href="Language-oriented_programming" title="Language-oriented programming">Language-oriented</a></li>

<li><a href="List_comprehension" title="List comprehension">List comprehension</a></li>

<li><a href="Modeling_language" title="Modeling language">Modeling</a></li>

<li><a href="Natural-language_programming" class="mw-redirect" title="Natural-language programming">Natural language</a></li>

<li><a href="Non-English-based_programming_languages" title="Non-English-based programming languages">Non-English-based</a></li>

<li><a href="Page_description_language" title="Page description language">Page description</a></li>

<li><a href="Pipeline_(software)" title="Pipeline (software)">Pipes</a> and <a href="Filter_(software)" title="Filter (software)">filters</a></li>

<li><a href="Probabilistic_programming" title="Probabilistic programming">Probabilistic</a></li>

<li><a href="Quantum_programming" title="Quantum programming">Quantum</a></li>

<li><a href="Scientific_programming_language" title="Scientific programming language">Scientific</a></li>

<li><a href="Scripting_language" title="Scripting language">Scripting</a></li>

<li><a href="Set_theoretic_programming" title="Set theoretic programming">Set-theoretic</a></li>

<li><a href="Simulation_language" title="Simulation language">Simulation</a></li>

<li><a href="Stack-oriented_programming" title="Stack-oriented programming">Stack-based</a></li>

<li><a href="System_programming_language" title="System programming language">System</a></li>

<li><a href="Tactile_programming_language" title="Tactile programming language">Tactile</a></li>

<li><a href="Template_processor" title="Template processor">Templating</a></li>

<li><a href="Transformation_language" title="Transformation language">Transformation</a> (<a href="Graph_rewriting" title="Graph rewriting">Graph rewriting</a>, <a href="Production_system_(computer_science)" title="Production system (computer science)">Production</a>, <a href="Pattern_matching" title="Pattern matching">Pattern</a>)</li>

<li><a href="Visual_programming_language" title="Visual programming language">Visual</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Concurrent_computing" title="Concurrent computing">Concurrent</a>,<br><a href="Distributed_computing" title="Distributed computing">distributed</a>,<br><a href="Parallel_computing" title="Parallel computing">parallel</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Actor_model" title="Actor model">Actor-based</a></li>

<li><a href="Automatic_mutual_exclusion" title="Automatic mutual exclusion">Automatic mutual exclusion</a></li>

<li><a href="Choreographic_programming" title="Choreographic programming">Choreographic programming</a></li>

<li><a href="Concurrent_logic_programming" title="Concurrent logic programming">Concurrent logic</a> (<a href="Concurrent_constraint_logic_programming" title="Concurrent constraint logic programming">Concurrent constraint logic</a>)</li>

<li><a href="Concurrent_object-oriented_programming" title="Concurrent object-oriented programming">Concurrent OO</a></li>

<li><a href="Macroprogramming" title="Macroprogramming">Macroprogramming</a></li>

<li><a href="Multitier_programming" title="Multitier programming">Multitier programming</a></li>

<li><a href="Organic_computing" title="Organic computing">Organic computing</a></li>

<li><a href="Parallel_programming_model" title="Parallel programming model">Parallel programming models</a></li>

<li><a href="Partitioned_global_address_space" title="Partitioned global address space">Partitioned global address space</a></li>

<li><a href="Process-oriented_programming" title="Process-oriented programming">Process-oriented</a></li>

<li><a href="Relativistic_programming" title="Relativistic programming">Relativistic programming</a></li>

<li><a href="Service-oriented_programming" title="Service-oriented programming">Service-oriented</a></li>

<li><a href="Structured_concurrency" title="Structured concurrency">Structured concurrency</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Metaprogramming" title="Metaprogramming">Metaprogramming</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Attribute-oriented_programming" title="Attribute-oriented programming">Attribute-oriented</a></li>

<li><a href="Automatic_programming" title="Automatic programming">Automatic</a> (<a href="Inductive_programming" title="Inductive programming">Inductive</a>)</li>

<li><a href="Dynamic_programming_language" title="Dynamic programming language">Dynamic</a></li>

<li><a href="Extensible_programming" title="Extensible programming">Extensible</a></li>

<li><a href="Generic_programming" title="Generic programming">Generic</a></li>

<li><a href="Homoiconicity" title="Homoiconicity">Homoiconicity</a></li>

<li><a href="Interactive_programming" title="Interactive programming">Interactive</a></li>

<li><a href="Macro_(computer_science)" title="Macro (computer science)">Macro</a> (<a href="Hygienic_macro" title="Hygienic macro">Hygienic</a>)</li>

<li><a href="Metalinguistic_abstraction" title="Metalinguistic abstraction">Metalinguistic abstraction</a></li>

<li><a href="Multi-stage_programming" title="Multi-stage programming">Multi-stage</a></li>

<li><a href="Program_synthesis" title="Program synthesis">Program synthesis</a> (<a href="Bayesian_program_synthesis" title="Bayesian program synthesis">Bayesian</a>, <a href="Inferential_programming" title="Inferential programming">Inferential</a>, <a href="Programming_by_demonstration" title="Programming by demonstration">by demonstration</a>, <a href="Programming_by_example" title="Programming by example">by example</a>)</li>

<li><a href="Reflective_programming" title="Reflective programming">Reflective</a></li>

<li><a href="Self-modifying_code" title="Self-modifying code">Self-modifying code</a></li>

<li><a href="Symbolic_programming" title="Symbolic programming">Symbolic</a></li>

<li><a href="Template_metaprogramming" title="Template metaprogramming">Template</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Separation_of_concerns" title="Separation of concerns">Separation<br>of concerns</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Aspect-oriented_programming" title="Aspect-oriented programming">Aspects</a></li>

<li><a href="Component-based_software_engineering" title="Component-based software engineering">Components</a></li>

<li><a href="Data-driven_programming" title="Data-driven programming">Data-driven</a></li>

<li><a href="Data-oriented_design" title="Data-oriented design">Data-oriented</a></li>

<li><a href="Event-driven_programming" title="Event-driven programming">Event-driven</a></li>

<li><a href="Feature-oriented_programming" title="Feature-oriented programming">Features</a></li>

<li><a href="Literate_programming" title="Literate programming">Literate</a></li>

<li><a href="Role-oriented_programming" title="Role-oriented programming">Roles</a></li>

<li><a href="Subject-oriented_programming" title="Subject-oriented programming">Subjects</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Types_of_programming_languages107" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Types_of_programming_languages107" style="font-size:114%;margin:0 4em"><a href="Programming_paradigm" title="Programming paradigm">Types of programming languages</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Level</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Machine_code" title="Machine code">Machine</a></li>

<li><a href="Assembly_language" title="Assembly language">Assembly</a></li>

<li><a href="Compiled_language" title="Compiled language">Compiled</a></li>

<li><a href="Interpreted_language" class="mw-redirect" title="Interpreted language">Interpreted</a></li></ul>

<ul><li><a href="Low-level_programming_language" title="Low-level programming language">Low-level</a></li>

<li><a href="High-level_programming_language" title="High-level programming language">High-level</a></li>

<li><a href="Very_high-level_programming_language" title="Very high-level programming language">Very high-level</a></li>

<li><a href="Esoteric_programming_language" title="Esoteric programming language">Esoteric</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Programming_language_generations" title="Programming language generations">Generation</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="First-generation_programming_language" title="First-generation programming language">First</a></li>

<li><a href="Second-generation_programming_language" title="Second-generation programming language">Second</a></li>

<li><a href="Third-generation_programming_language" title="Third-generation programming language">Third</a></li>

<li><a href="Fourth-generation_programming_language" title="Fourth-generation programming language">Fourth</a></li>

<li><a href="Fifth-generation_programming_language" title="Fifth-generation programming language">Fifth</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q528588#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata821" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q528588#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata821" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh94003833">United States</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://catalogue.bnf.fr/ark:/12148/cb124026426">France</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://data.bnf.fr/ark:/12148/cb124026426">BnF data</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.nli.org.il/en/authorities/987007539402305171">Israel</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/concept/b86a17af-a18f-4bca-998b-3bbf7db3862e">Yale LUX</a></span></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-27" href="https://en.wikipedia.org/wiki/?title=Constraint_programming&oldid=1292513929">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>